package my.study.java.basic.algorithm.sorts;

import java.util.Random;

/**
 * 插入排序就像摸牌一下，手中的牌一直都是排好序的，新的牌插到这个已排序序列中
 * 最佳情况：T(n) = O(n) 顺序
 * 最坏情况：T(n) = O(n^2) 逆序
 * 
 * @author fanhongjie
 * 
 */
public class InsertSort {
	private static final int N = 20;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Element array[] = new Element[N];
		Random random = new Random();
		for (int i = 0; i < N; i++) {
			array[i] = new Element(random.nextInt(2 * N));
		}
		System.out.print("Init:\t");
		for (int i = 0; i < N; i++) {
			System.out.print(array[i].getValue() + "\t");
		}
		System.out.println();
		// Insert Sort()
		for (int i = 1; i <= N - 1; i++) {
			int j = i;
			Element temp = array[i];
			while (j >= 1 && temp.compareTo(array[j - 1]) < 0) {
				array[j] = array[j - 1];
				j--;
			}
			array[j] = temp;
			System.out.print(i + ":\t");
			for (int k = 0; k < N; k++) {
				System.out.print(array[k].getValue() + "\t");
			}
			System.out.println();
		}

		System.out.print("Result:\t");
		for (int i = 0; i < N; i++) {
			System.out.print(array[i].getValue() + "\t");
		}
		System.out.println();
	}

}
